package bin_tree.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author shkstart
 * 判断平衡树
 * @create 2022-10-17-18:35
 */
public class Num110 {
    Map<TreeNode,Integer> map = new HashMap<>();
    public boolean isBalanced(TreeNode root) {

//        边界
        if(root==null){
            return true;
        }

//        使用Map存储节点的高度

        int leftHeight=0;
        int rightHeight=0;
        if (map.containsKey(root.left)) {
//            root.left节点的高度已经计算过一次
            leftHeight = map.get(root.left);
        }else{
//            通过递归函数计算该节点的高度，存入map中
            leftHeight = height(root.left);
            map.put(root.left,leftHeight);
        }

        if (map.containsKey(root.right)) {
//            root.left节点的高度已经计算过一次
            rightHeight = map.get(root.right);
        }else{
//            通过递归函数计算该节点的高度，存入map中
            rightHeight = height(root.right);
            map.put(root.right,rightHeight);
        }

////        判断当前root的左右子树高度
//        int leftHeight = height(root.left);
//        int rightHeight = height(root.right);
        int heightAbs = Math.abs(leftHeight - rightHeight);

        if (heightAbs > 1) {
            return false;
        }
//        递归查看子树是否是平衡树
        return isBalanced(root.left) && isBalanced(root.right);
    }
//    求书的高度
    public int height(TreeNode root){
        if(root==null){
            return 0;
        }
        return 1 + Math.max(height(root.left), height(root.right));
    }
}
